#include <iostream>

using namespace std;

/*
Question: given an array of three different kinds of value such as array(1, 2, 0, 2, 1) and array(a, b, a, c, b), 
write an algorithm to sort the array. 
For example, input array(1, 2, 0, 2, 1) becomes array(0, 1, 1, 2, 2) and input array(a, b, a, c, b) becomes array(a, a, b, b, c).

http://codesam.blogspot.com/2011/04/sorting-array-of-three-kinds-or-dutch.html

*/

void dutchFlagSort(int inArray[], int arraySize, int high, int low)
{
  if (arraySize == 0)
    return;

  int lower = 0;
  while (inArray[lower] == low && lower < arraySize)
    lower++;

  int upper = arraySize - 1;
  while (inArray[upper] == high && upper >= 0)
    upper--;

  int temp = 0;
  int pivot;
  for (pivot = lower; pivot <= upper;)
  {
    if (inArray[pivot] == low)
    {
      temp = inArray[pivot];
      inArray[pivot] = inArray[lower];
      inArray[lower] = temp;
      pivot++;
      lower++;
    }
    else if (inArray[pivot] == high)
    {
      temp = inArray[pivot];
      inArray[pivot] = inArray[upper];
      inArray[upper] = temp;
      upper--;
    }
    else
      pivot++;
  }
}

void main()
{
    int arr[] = {1, 2, 0, 0, 2, 1, 1, 0};
    dutchFlagSort(arr, 8, 7, 0);
}

